package com.heima.datastructure.deque;

import java.util.Iterator;

/**
 * 用循环数组实现双端队列方法三
 *
 * @author 勾新杰
 * @version 1.0
 * @date 2024/9/2 18:39
 */
public class ArrayDeque3<E> implements Deque<E>, Iterable<E> {
    private E[] arr; // 数组，这里我们把数组的长度定为2^n
    private int head; // 头指针，与容量模运算后指向头元素，默认初始化为0
    private int tail; // 尾指针，与容量模运算后指向尾元素的下一个元素，默认初始化为0
    private final static int defaultCapacity = 8; // static修饰的变量属于类，不属于实例对象，在创建实例时（堆）是不会开辟static修饰的相关变量（类的元空间）的空间的，

    /**
     * 用构造方法初始化
     *
     * @param capacity 容量
     */
    @SuppressWarnings("all")
    public ArrayDeque3() {
        arr = (E[]) new Object[defaultCapacity]; // 不用考虑head和tail
    }

    /**
     * 用构造方法初始化
     *
     * @param capacity 容量，会变成大于等于capacity的最近的2的n次方的数
     */
    @SuppressWarnings("all")
    public ArrayDeque3(int capacity) {
        capacity = nearest2N(capacity);
        arr = (E[]) new Object[capacity];
    }

    /**
     * 计算head和tail的真实索引
     *
     * @param inaccurateIndex 传入的不真实索引
     * @return 真实索引
     */
    private int calculateIndex(int inaccurateIndex) {
        return inaccurateIndex & (arr.length - 1);
    }

    /**
     * 向双端队列左端加入元素
     *
     * @param value 待入队的值
     * @return 入队成功返回true
     */
    @Override
    public boolean offerFirst(E value) {
        if (isFull()) {
            return false;
        }
        int headIndex = calculateIndex(--head);
        arr[headIndex] = value;
        return true;
    }

    /**
     * 向双端队列右端加入元素
     *
     * @param value 待入队的值
     * @return 入队成功返回true
     */
    @Override
    public boolean offerLast(E value) {
        if (isFull()) {
            return false;
        }
        int tailIndex = calculateIndex(tail++);
        arr[tailIndex] = value;
        return true;
    }

    /**
     * 向双端队列左端获取元素并删除
     *
     * @return 双端队列左端获取元素
     */
    @Override
    public E pollFirst() {
        if (isEmpty()) {
            return null;
        }
        int headIndex = calculateIndex(head++);
        E value = arr[headIndex];
        arr[headIndex] = null;
        return value;
    }

    /**
     * 向双端队列右端获取元素并删除
     *
     * @return 双端队列右端获取元素
     */
    @Override
    public E pollLast() {
        if (isEmpty()) {
            return null;
        }
        int tailIndex = calculateIndex(--tail);
        E value = arr[tailIndex];
        arr[tailIndex] = null;
        return value;
    }

    /**
     * 向双端队列左端获取元素
     *
     * @return 双端队列左端获取元素
     */
    @Override
    public E peekFirst() {
        if (isEmpty()) {
            return null;
        }
        return arr[calculateIndex(head)];
    }

    /**
     * 向双端队列右端获取元素
     *
     * @return 双端队列右端获取元素
     */
    @Override
    public E peekLast() {
        if (isEmpty()) {
            return null;
        }
        return arr[calculateIndex(tail - 1)];
    }

    /**
     * 判断是否为空
     *
     * @return 为空返回true
     */
    @Override
    public boolean isEmpty() {
        return tail - head == 0;
    }

    /**
     * 判断是否为满
     *
     * @return 为满返回true
     */
    @Override
    public boolean isFull() {
        return tail - head == arr.length;
    }

    /**
     * 获取双端队列大小
     *
     * @return 大小
     */
    @Override
    public int size() {
        return tail - head;
    }

    /**
     * 迭代器
     *
     * @return 迭代器
     */
    @Override
    public Iterator<E> iterator() {
        return new Iterator<E>() {
            int index = head;

            @Override
            public boolean hasNext() {
                return index != tail;
            }

            @Override
            public E next() {
                return arr[calculateIndex(index++)];
            }
        };
    }

    /**
     * 扩容，默认扩容到原来的两倍
     */
    public void expansion() {
        expansion(arr.length * 2);
    }

    /**
     * 扩容
     *
     * @param capacity 容量
     * @throws IllegalArgumentException 传入的容量大小小于原始的容量大小
     */
    @SuppressWarnings("all")
    public void expansion(int capacity) {
        capacity = nearest2N(capacity);
        if (capacity <= arr.length) {
            throw new IllegalArgumentException("参数" + capacity + "不能小于或等于" + arr.length);
        }
        E[] array = (E[]) new Object[capacity];
        int index = 0;
        for (E value : this) {
            array[index++] = value;
        }
        head = 0;
        tail = index;
        arr = array; // arr指向的原来的数组对象没有变量指向它，会被垃圾回收机制回收
    }

    /**
     * 判断number是否是2的n次方
     *
     * @param number number
     * @return 是返回true
     */
    private boolean is2N(int number) {
        return (number & (number - 1)) == 0;
    }

    /**
     * 计算0或正整数num的正整数n次方，不考虑溢出问题
     *
     * @param base     底数，正整数或0
     * @param exponent 幂，正整数
     * @return 计算结果
     */
    private int power(int base, int exponent) {
        if (exponent == 0) {
            return 1;
        }
        if (base == 2) {
            return 1 << exponent;
        }
        return base * power(base, exponent - 1);
    }

    /**
     * 寻找比大于等于number的最近的2的n次方的数
     *
     * @param number number
     * @return 满足条件的数
     * @throws IllegalArgumentException number为负数或者number太大了
     */
    private int nearest2N(int number) {
        if (number < 0) {
            throw new IllegalArgumentException("参数" + number + "不合法，number不能为负数");
        }
        if (is2N(number)) {
            return number;
        }
        number |= number >> 1;
        number |= number >> 2;
        number |= number >> 4;
        number |= number >> 8;
        number |= number >> 16;
        number += 1;
        if (number == Integer.MAX_VALUE) {
            throw new IllegalArgumentException("参数" + number + "不合法，太大了");
        }
        return number;
    }
}
